//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
//
// Related Topics 字符串 动态规划 回溯与递归 👍 3220 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function generateParenthesis(n: number): string[] {
//? 必须严格右括号剩余数量必须大于剩余左括号数量，我们才能选右括号
    let res = [];
    function backtracking(cur, left, right) {
        if (cur.length === 2 * n) {
            res.push(cur);
            return;
        }
        //? 左括号还存在，就可以选左括号
        if (left > 0) backtracking(cur + "(", left - 1, right);
        //? 右括号数量要大于左括号，才可以选右括号
        if (right > left) backtracking(cur + ")", left, right - 1);
    };
    backtracking("", n, n);
    return res;
};
//leetcode submit region end(Prohibit modification and deletion)
